package 搜索算法.深度优先搜索;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 1. 问题描述
 *      节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
 *
 * 2. 算法分析
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 节点之间的通路 {

    // dfs 非递归实现
    public boolean findWhetherExistsPath1(int n, int[][] graph, int start, int target) {
        if(n == 0) {
            return false;
        }
        // 存放图的所有有向边
        List<List<Integer>> edges = new ArrayList<>();
        for(int i = 0; i < graph.length; i++) {
            List<Integer> edge = new ArrayList<>();
            edge.add(graph[i][0]);
            edge.add(graph[i][1]);
            edges.add(edge);
        }
        boolean[] vis = new boolean[n];
        Stack<Integer> stack = new Stack<>();
        stack.push(start);
        while(!stack.isEmpty()) {
            int top = stack.pop();
            vis[top] = true;
            for(List<Integer> edge : edges) {
                if(edge.get(0) == top && vis[edge.get(1)] == false) {
                    if(edge.get(1) == target) {
                        return true;
                    }
                    stack.push(edge.get(1));
                    vis[edge.get(1)] = true;
                }
            }
        }
        return false;
    }

    // dfs 递归实现  采用逆序压缩法  没有超出时间限制
    public boolean findWhetherExistsPath2(int n, int[][] graph, int start, int target) {
        if(n == 0) {
            return false;
        }
        int edgeCount = graph.length; // 获取所有的边的数量
        boolean[] vis = new boolean[edgeCount]; // 边的访问状态数组
        for (int i = 0; i < edgeCount; i++) { // 扫描所有边
            // 判断当前边是否有被访问过，如果没有才继续这条边进行搜索
            if (!vis[i]) { // 如果没有被访问
                // 判断当前边是否连接给定的两个点
                if (graph[i][0] == start && graph[i][1] == target) {
                    return true;
                }
                // 修改边的访问状态
                vis[i] = true;
                // 判断当前边是否已target为终点，如果是，搜索路径可以压缩到start到graph[i][0]
                // 所以此时我们只需要判断当前终点是否为target 并且 递归调用findWhetherExistsPath方法判断返回值
                // 如果为true，则表明找到直接返回true，如果没有，将当前边的访问状态还原
                if (graph[i][1] == target && findWhetherExistsPath2(n, graph, start, graph[i][0])) {
                    return true;
                }
                vis[i] = false;
            }
        }
        return false;
    }

    // dfs 递归实现  采用正序压缩法  超出时间限制 (为什么正序会慢这么多?)
    public boolean findWhetherExistsPath3(int n, int[][] graph, int start, int target) {
        if (n == 0) {
            return false;
        }
        int edgeCount = graph.length;
        boolean[] vis = new boolean[edgeCount];
        for (int i = 0; i < edgeCount; i++) {
            if (!vis[i]) {
                if (graph[i][0] == start && graph[i][1] == target) {
                    return true;
                }
                vis[i] = true;
                if (graph[i][0] == start && findWhetherExistsPath3(n,graph,graph[i][1],target)) {
                    return true;
                }
                vis[i] = false;
            }
        }
        return false;
    }

    // dfs 非递归  采用领接表实现图的存储
    public boolean findWhetherExistsPath4(int n, int[][] graph, int start, int target) {
        // 1. 将有向图使用领接表来存储
        ArrayList<Integer>[] disjoint = new ArrayList[n];
        for(int i = 0; i < n; i++) {
            disjoint[i] = new ArrayList<>();
        }
        int edgeCount = graph.length;
        for(int i = 0; i < edgeCount; i++) {
            disjoint[graph[i][0]].add(graph[i][1]);
        }
        // 2. dfs非递归过程
        boolean[] vis = new boolean[n]; // 点的访问数组
        Stack<Integer> stack = new Stack<>(); // 创建辅助栈
        stack.push(start); // 起点入栈
        while(!stack.isEmpty()) {
            int top = stack.pop(); // 起点索引
            vis[top] = true;
            for(Integer x : disjoint[top]) { // 访问与当前起点相连的所有点
                if(x == target) {
                    return true;
                }
                stack.push(x);
            }
        }
        return false;
    }
}
